package test.algos.sorting.quicksort;

import static test.algos.sorting.input.InputData.INPUT_DATA;

import java.util.ArrayList;
import java.util.List;

import test.algos.sorting.Sort;

public class QuickSort implements Sort {

	private List<Integer> inputData;

	private PivotChooser pivotChooser;

	public QuickSort() {
		this(INPUT_DATA, new FirstElemPivot());
	}

	public QuickSort(List<Integer> inputData, PivotChooser pivotChooser) {
		this.inputData = inputData;
		this.pivotChooser = pivotChooser;

	}

	@Override
	public void sort() {

		System.out.println("Before Sort:" + inputData);

		DivideStep initDivideStep = new DivideStep(inputData);
		List<DivideStep> outSubLists = new ArrayList<>();

		outSubLists.add(initDivideStep);

		while (!outSubLists.isEmpty()) {
			outSubLists = buildSubLists(outSubLists);

		}

		System.out.println("After Sort:" + inputData);

	}

	private List<DivideStep> buildSubLists(List<DivideStep> inSubLists) {

		List<DivideStep> outSubLists = new ArrayList<>();

		for (DivideStep listIndex : inSubLists) {
			List<Integer> curInput = listIndex.getSubList();
			if (curInput.size() > 1) {
				Integer pivotIndex = quickSort(curInput);
				if (pivotIndex != null) {
					listIndex.setPivotIndex(pivotIndex);
					outSubLists.add(listIndex.getLeftPartition());
					outSubLists.add(listIndex.getRightPartition());
				}

			}

		}

		return outSubLists;

	}

	private Integer quickSort(List<Integer> curInput) {

		Integer pivotIndex = pivotChooser.choosePivot(curInput);
		if (pivotIndex != null) {
			Partitioner partition = new Partitioner(curInput);
			int curPivotIndex = partition.partition(pivotIndex);
			return curPivotIndex;
		}

		return pivotIndex;

	}

}
